package com.zjj.algorithm.learning.atguigu.linkedlist;

/**
 * @author zjj_admin
 * @date 2022/11/7 20:44
 */
public class Josepfo {

    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addKids(59);
        circleSingleLinkedList.play();
        circleSingleLinkedList.play(1,6);
    }

}



class CircleSingleLinkedList{

    /**
     * 第一个小孩，不会变
     */
    private Kid first = null;

    /**
     * 添加小孩
     * @param num 小孩的个数
     */
    public void addKids(int num){
        if(num < 1) {
            System.out.println("小孩数量错误，不能进行游戏");
            return;
        }
        //辅助指针，帮助构建环形链表
        Kid currKid = null;
        for (int i = 1; i <= num; i++) {
            Kid kid = new Kid(i);
            if (i==1) {
                first = kid;
                // 使之形成一个环
                first.setNext(first);
                //让当前指针指向第一个小孩
                currKid = kid;
            }else {
                currKid.setNext(kid);
                kid.setNext(first);
                currKid = kid;
            }
        }

    }


    /**
     * 玩耍
     */
    public void play(){
        if (first == null) {
            System.out.println("没有小孩，不能游戏！！！");
            return;
        }
        Kid currKid = first;
        while (true){
            System.out.printf("%d 号小孩正在玩\n",currKid.getNo());
            if(currKid.getNext() == first){
                break;
            }
            currKid = currKid.getNext();
        }
    }

    /**
     * 除权游戏
     * @param startNum 开始节点
     * @param countNum 每一次数几个小孩
     */
    public void play(int startNum,int countNum){
        if(this.first == null || startNum <1){
            System.out.println("输入参数有误，请重新输入");
            return;
        }

        //设置赋值指针，会让其指向最后一个节点
        Kid helper = first;
        while (true){
            //指向了最后一个节点
            if(helper.getNext() == first){
                break;
            }
            //后移
            helper = helper.getNext();
        }
        //这时helper已经指向了 first 的后一个节点
        for (int i = 0; i < startNum - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }

        while (true){
            if(helper == first){
                break;
            }
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            // 这时first指向的节点，就是要出圈的小鬼节点
            System.out.printf("小孩 %d 出圈\n", first.getNo());
            // 这时将first指向的小孩节点出圈
            first = first.getNext();
            //继续让 helper 执行最后一个节点
            helper.setNext(first);
        }
        System.out.printf("最后留在圈中的小孩编号 %d \n", first.getNo());
    }

}

/**
 * 节点，每一个节点表示一个小孩
 */
class Kid{

    /**
     * 节点编号
     */
    private int no;
    /**
     * 下一个节点
     */
    private Kid next;

    public Kid(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Kid getNext() {
        return next;
    }

    public void setNext(Kid next) {
        this.next = next;
    }
}
